package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class GenerateParentheses {

	public static void main(String[] args) {
		GenerateParentheses ins = new GenerateParentheses();
		
		List<String> res1 = ins.generateParenthesis(3);
		LeetCodeHelpers.printGenericList(res1);
	}
	
	public List<String> generateParenthesis(int n) {
		List<String> res = new ArrayList<String>();
		if (n <= 0) return res;
		
		this.generatePair("", 0, 0, n, res);
		return res;
	}
	
	// This is another line of thinking, keep inserting (, and then ), if count(right) < count(left), keep inserting right
	private void generatePair(String s, int leftCount, int rightCount, int n, List<String> res) {
		if ((leftCount + rightCount) == 2 * n) {
			res.add(s);
			return;
		}
		
		if (leftCount < n) {
			s += "(";
			generatePair(s, ++leftCount, rightCount, n, res);
			s = s.substring(0, s.length() - 1);
			leftCount--;
		}
		
		if (rightCount < leftCount) {
			s += ")";
			generatePair(s, leftCount, ++rightCount, n, res);
			s = s.substring(0, s.length() - 1);
		}
	}
	
	
	//**************************************
	// It's a question from CC150, my solution is inserting into string, which sounds complicated
	public List<String> generateParenthesisInsert(int n) {
		List<String> res = new ArrayList<String>();
		if (n <= 0) return res;
		
		// There will be many dups, so use a set
		Set<String> set = new HashSet<String>();
		this.helper("", 0, 0, n, set);
		
		res.addAll(set);
		return res;
	}
	
	private void helper(String s, int index, int count, int n, Set<String> set) {
		if (count == n) {
			set.add(s);
			return;
		}
		// Still a typical recursion with a for, remember to reset the count, this is exponential complexity
		for (int i = index; i <= s.length(); i++) {
			String t = this.insertParentheses(s, i);
			count++;
			helper(t, i, count, n, set);
			count--;
		}
	}
	
	private String insertParentheses(String s, int index) {
		String left = s.substring(0, index);
		String right;
		if (index == s.length()) {
			right = "";
		} else {
			right = s.substring(index, s.length());
		}
		return left + "()" + right;
	}

}
